package Offer11_旋转数组的最小数字;

import java.util.Arrays;

/**
 * --------------------------------------------------------------------------------------------------------------
 * 题目：
 *      把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 *      给你一个可能存在重复元素值的数组numbers，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。
 *      请返回旋转数组的最小元素。例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
 *      注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 * --------------------------------------------------------------------------------------------------------------
 * 示例：
 *      输入：numbers = [3,4,5,1,2]
 *      输出：1
 * -------------------------------------------------------------------------------------------------------------
 * 方法：
 *      方法1：二分查找
 *      方法2：将数组排序，然后直接输出number[0]
 * --------------------------------------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        int[] numbers = new int[]{3,4,5,1,2};
        System.out.println(minArray1(numbers));
        System.out.println(minArray2(numbers));
    }
    public static int minArray1(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        while(left<right){
            int mid = (left+right)/2;
            if(numbers[mid]>numbers[right]){
                left=mid+1;
            }else if(numbers[mid]<numbers[right]){
                right=mid;
            }else{
                right-=1;
            }
        }
        return numbers[left];
    }

    public static int minArray2(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }
}
